#include <iostream>
#include <cstring>
#include <unordered_map>
#include <climits>
#include <vector>
#include <stack>
#include <list>

using namespace std;

namespace {

// 最长不重复子串长度
int lengthOfLongestSubstring(string s) {
    int left = 0, right = 0;
    unordered_map<char, int> window;

    int res = 0;
    while (right < s.length()) {
        char c1 = s[right];
        window[c1]++;
        right++;

        while (window[c1] > 1) {
            char c2 = s[left];
            window[c2]--;
            left++;
        }

        // std::cout << res << "," << right << "," << left << std::endl;
        res = max(res, right - left);
    }
    return res;
}

// s1中包含s2的所有字符的最小子串
string minWindow(string s1, string s2) {
    int left = 0, right = 0;
    int start = 0, minLen = INT_MAX;
    unordered_map<char, int> window;
    unordered_map<char, int> needs;
    for (char c : s2) needs[c]++;

    int match = 0;
    while (right < s1.length()) {
        char c1 = s1[right];
        if (needs.count(c1) > 0) {
            window[c1]++;
            if (window[c1] == needs[c1]) {
                // 字符c1的出现次数符合要求
                match++;
            }
        }
        right++;

        while (match == s2.length()) {
            if (right - left < minLen) {
                start = left;
                minLen = right - left;
            }

            // 缩小左边
            char c2 = s1[left];
            if (needs[c2] > 0) {
                window[c2]--;
                if (window[c2] < needs[c2]) {
                    match--;
                }
            }
            left++;
        }
    }

    return minLen == INT_MAX ? "" : s1.substr(start, minLen);
}

typedef std::vector<int> VectorInt;

VectorInt findAnagrams(string s1, string s2) {
    int left = 0, right = 0;
    VectorInt res;
    unordered_map<char, int> window;
    unordered_map<char, int> needs;
    for (char c : s2) needs[c]++;

    int match = 0;
    while (right < s1.length()) {
        char c1 = s1[right];
        if (needs.count(c1) > 0) {
            window[c1]++;
            if (window[c1] == needs[c1]) {
                // 字符c1的出现次数符合要求
                match++;
            }
        }
        right++;

        while (match == s2.length()) {
            if (right - left == s2.length()) {
                res.push_back(left);
            }

            // 缩小左边
            char c2 = s1[left];
            if (needs[c2] > 0) {
                window[c2]--;
                if (window[c2] < needs[c2]) {
                    match--;
                }
            }
            left++;
        }
    }

    return res;
}

int calculate(std::list<char> &s) {
    stack<int> stk;

    int pre = 0;
    int num = 0;
    char sign = '+';
    while (s.size() > 0) {
        char c = s.front();
        s.pop_front();
        if (isdigit(c))
            num = num * 10 + (c - '0');
        else if (c == '(') {
            num = calculate(s);
        }

        std::cout << "num " << num << ":" << c << ", ";
        if ((!isdigit(c) && c != ' ') || s.size() == 0) {
            switch (sign) {
                case '+':
                    stk.push(num); break;
                case '-':
                    stk.push(-num); break;
                case '*':
                    pre = stk.top();
                    stk.pop();
                    stk.push(pre * num);
                    break;
                case '/':
                    pre = stk.top();
                    stk.pop();
                    stk.push(pre / num);
                    break;
            }
            sign = c;
            num = 0;
        }

        if (c == ')') break;
    }

    int res = 0;
    while (!stk.empty()) {
        std::cout << stk.top() << ",";
        res += stk.top();
        stk.pop();
    }
    std::cout << " res " << res << std::endl;
    return res;
}

int calculate(string s) {
    std::list<char> lst(s.begin(), s.end());
    return calculate(lst);
}

void Handle() {
    string s = "abccxbacbd";
    std::cout << "lenght of longest substring " << lengthOfLongestSubstring(s) << std::endl;

    string s2 = "cxa";
    std::cout << "min window " << minWindow(s, s2) << std::endl;

    string s3 = "abc";
    VectorInt res = findAnagrams(s, s3);
    for (int n : res) {
        std::cout << n << ",";
    }
    std::cout << std::endl;

    string cal = "1 + (2/(5*6+7) - 99*8+5) - 200";
    std::cout << cal << " = " << calculate(cal) << std::endl;
}

}

void HandleSlideWindow() {
    Handle();
}
